package top.fengleifeng.question;

/**
 * @author : fengelfeing
 * @Package : top.fengleifeng.question
 * @Description:
 * @Date: 2020年10月28日8:25 下午
 */
public class Num1283使结果不超过阈值的最小除数 {
    /**
     * 思路：
     * 需要二分查找对threshold
     */
    class Solution {
        public int smallestDivisor(int[] nums, int threshold) {
            int max = nums[0];
            for (int num:nums)
                max=Integer.max(max,num);
            int left = 1, right = max;
            while (left < right) {
                int mid = (left+right)/2;
                int i = calculateSum(nums, mid);
                if (i > threshold) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            return right;
        }

        private int calculateSum(int[] nums, int divisor) {
            int sum = 0;
            for (int num : nums) {
                sum += num / divisor;

                // 注意：不能整除的时候，需要向上取整
                if (num % divisor != 0) {
                    sum++;
                }
            }
            return sum;
        }

    }

    public static void main(String[] args) {
        int[] ints = {1, 2, 5, 9};
        int i = 6;
        int i1 = new Num1283使结果不超过阈值的最小除数().new Solution().smallestDivisor(ints, i);
        System.out.println(i1);
    }
}
